public class TreePriorityQueue implements PriorityQueue {

	private BinarySearchTree bst;
	private int size;

	
	private static class Value implements Comparable {
		ArrayQueue items;
		
		Value() {
			items = new ArrayQueue();
		}

		public boolean equals( Object obj ) {
			if ( obj instanceof Value ) {
				return compareTo( obj ) == 0;
			}
			else {
				return false;
			}
		}

		public int compareTo( Object obj ) {
			Value other = (Value)obj;
			Comparable item = (Comparable)items.first();
			return item.compareTo( other.items.first() );
		}
	}
	

	public TreePriorityQueue() {
		init();
	}


	private void init() {
		bst = new BinarySearchTree();
		size = 0;
	}


    public void insert( Comparable x ) {
		Value newVal = new Value();
		newVal.items.enqueue( x );

		Value val = (Value)bst.find( newVal );
		if ( val != null ) {
			val.items.enqueue( x );
		}
		else {
			bst.insert( newVal );
		}

		++size;
	}


    public Comparable findMin( ) {
		if ( isEmpty() ) {
			throw new IllegalStateException();
		}
		else {
			Value minVal = (Value)bst.findMin();
			return (Comparable)minVal.items.first();
		}
	}


    public Comparable deleteMin( ) {
		if ( isEmpty() ) {
			throw new IllegalStateException();
		}
		else {
			Value minVal = (Value)bst.findMin();
			Comparable minItem = (Comparable)minVal.items.first();

			if ( minVal.items.size() == 1 ) {
				bst.remove( minVal );
			}
			else {
				minVal.items.dequeue();
			}

			--size;

			return minItem;
		}
	}


    public boolean isEmpty( ) {
		return size == 0;
	}


    public void makeEmpty( ) {
		init();
	}
    

    public int size( ) {
		return size;
	}

}